import java.util.Stack;

/**
 * 394. 字符串解码
 * https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked
 */
class Solution {
    public String decodeString(String s) {
        Stack<Integer> stack1 = new Stack<>();// 数字栈
        Stack<StringBuilder> stack2 = new Stack<>();// 字符栈
        char[] ch = s.toCharArray();
        int n = ch.length;

        for(int i = 0; i < n; i++) {
            if(ch[i] >= '0' && ch[i] <= '9') {
                // 1、提取出所有数字，放进数字栈中
                int t = ch[i] - '0';
                while(i + 1 < n && ch[i + 1] >= '0' && ch[i + 1] <= '9') {
                    t = t * 10 + ch[i + 1] - '0';
                    i++;
                }
                stack1.push(t);
            } else if(ch[i] == '[') {
                // 2、提取出所有字符，放进字符栈中
                StringBuilder tmp = new StringBuilder();
                while(i + 1 < n && ch[i + 1] >= 'a' && ch[i + 1] <= 'z') {
                    char t = ch[i + 1];
                    tmp.append(t);
                    i++;
                }
                stack2.push(tmp);
            } else if(ch[i] == ']'){
                // 3、提取出字符占顶元素、数字栈顶元素，循环
                StringBuilder t = stack2.pop();
                StringBuilder tmp = new StringBuilder();
                if(!stack1.empty()) {
                    int m = stack1.pop();
                    for(int j = 0; j < m; j++) {
                        tmp.append(t);
                    }
                } else {
                    tmp.append(t);
                }
                // 拿出字符栈顶元素，再字符栈顶元素后面添加tmp
                if(!stack2.empty()) {
                    StringBuilder x = stack2.pop().append(tmp);
                    stack2.push(x);
                } else {
                    stack2.push(tmp);
                }
            } else{
                // 单单遇到字符了
                StringBuilder tmp = new StringBuilder();
                tmp.append(ch[i]);
                while(i + 1 < n && ch[i + 1] >= 'a' && ch[i + 1] <= 'z') {
                    tmp.append(ch[i + 1]);
                    i++;
                }
                // 拿出栈顶元素，给栈顶元素append
                if(!stack2.empty()) {
                    StringBuilder x = stack2.pop().append(tmp);
                    stack2.push(x);
                } else {
                    stack2.push(tmp);
                }

            }
        }

        return stack2.pop().toString();
    }
}